def sort_and_merge(left_nums, right_nums):
    left, right = 0, 0
    len_left, len_right = len(left_nums), len(right_nums)
    res = []
    while left < len_left and right < len_right:
        if left_nums[left] <= right_nums[right]:
            res.append(left_nums[left])
            left += 1
        else:
            res.append(right_nums[right])
            right += 1
    if left < len_left:
        res += left_nums[left:]
    if right < len_right:
        res += right_nums[right:]
    return res


def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left_nums, right_nums = nums[:mid], nums[mid:]
    res = sort_and_merge(merge_sort(left_nums), merge_sort(right_nums))
    return res


if __name__ == "__main__":
    nums = [4, 2, 3, 1]
    print(merge_sort(nums))
